// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const int N = 2e6+50;

int prime[N], pcnt, minp[N], pid[N];
void init() {
    for (int i=2; i<N; ++i) {
        if (!minp[i]) {
            minp[i] = i;
            pid[i] = pcnt;
            prime[pcnt++] = i;
        }
        for (int j=0; j<pcnt; ++j) {
            LL nextp = 1LL * i * prime[j];
            if (nextp >= N)
                break;
            if (!minp[nextp])
                minp[nextp] = minp[i];
            if (i % prime[j] == 0)
                break;
        }
    }
}

int n, a[N];

vector<int> getPrimeDiv(int x) {
    vector<int> res;
    // dbg(x);
    while (x > 1) {
        int p = minp[x];
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            ++cnt;
        }
        if (cnt & 1)
            res.push_back(pid[p]);
    }
    return res;
}

vector<int> dat[N];

vector<int> G[N];
int cntm;
void add(int u, int v) {
    
    if (u == v)
        return;
    ++cntm;
    // dbg(u, v);
    G[u].push_back(v);
    G[v].push_back(u);
}

set<pair<int, int>> edges;

namespace cy {
    int ans;

    int dep[N];
    int bfs(int s, int ans) {
        static int d[N], st, ed;
        static pair<int, int> q[N];
        st = ed = 0;
        memset(d, -1, 4 * pcnt);
        d[s] = 0;
        q[ed++] = make_pair(s, -1);
        while (st < ed) {
            auto p = q[st++];
            int now = p.first, fa = p.second;
            // if (s == 0)
            //     dbg(now);
            if (d[now] * 2 >= ans)
                return ans;
            for (int v : G[now]) {
                if (v == fa)
                    continue;
                if (~d[v]) {

                    // dbg(d[now], d[v], now, v);
                    return d[v] + d[now] + 1;
                }
                else {
                    d[v] = d[now] + 1;
                    q[ed++] = make_pair(v, now);
                }
            }
        }
        return 0x3f3f3f3f;
    }

    int go(int n) {
        int ans = 0x3f3f3f3f;
        for (int i=0; i<168; ++i) {
            // dbg(i, ans);
            ans = min(ans, bfs(i, ans));
        }
        return ans;
    }
}

bool on[N];

int tryst(int stx, int ans) {
    static int d[N];
    memset(d, 0x3f3f3f3f, 4 * (pcnt + 1));
    int n = pcnt;
    d[stx] = 0;

    static int q[N], st, ed;
    st = ed = 0;
    q[ed++] = stx;

    while (st < ed && d[q[st]] < ans) {
        int u = q[st++];
        // dbg(stx, u, d[u]);
        if (on[u] && u != stx)
            return d[u]+2;
        // dbg(stx, u, d[u]);
        for (int v : G[u]) {
            if (d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                q[ed++] = v;
            }
        }
    }
    return 0x3f3f3f3f;
}

int main(int argc, char const *argv[]) {
    // code
    init();


    // dbg(pcnt);
    // for (int i=0; i<pcnt; ++i) {
    //     if (prime[i] >= 1000) {
    //         dbg(i);
    //         break;
    //     }
    // }

    // n = 100000;

    // {
    //     int nn = 0;
    //     for (int i=0; i<pcnt; ++i)
    //         for (int j=i; j<pcnt; ++j) {
    //             LL x = 1LL * prime[i] * prime[j];
    //             if (x > 1000000)
    //                 break;
    //             a[nn++] = prime[i] * prime[j];
    //             if (nn == n)
    //                 break;
    //         }
    // }

    // dbg("data");

    scanf("%d", &n);

    bool flag = false;
    for (int i=0; i<n; ++i) {
        scanf("%d", &a[i]);
        // if (a[i] == 1) {
        //     puts("1");
        //     return 0;
        // }
        const auto &f = getPrimeDiv(a[i]);
        if (f.size() == 0) {
            puts("1");
            return 0;
        }
        pair<int, int> p;
        if (f.size() == 1) {
            p = make_pair(f[0], f[0]);
            // dbg(f[0]);
            on[f[0]] = true;
        } else
            p = make_pair(f[0], f[1]);
        if (p.first > p.second)
            swap(p.first, p.second);
        if (edges.count(p)) {
            flag = true;
        } else {
            edges.insert(p);
            add(p.first, p.second);
        }
    }
    if (flag) {
        puts("2");
        return 0;
    }
    vector<int> st;
    for (int i=0; i<pcnt; ++i) {
        if (on[i])
            st.push_back(i);
    }
    // if (st.size() > 168)
    //     return 0;
    // dbg(cntm);
    int ans = cy::go(pcnt);
    dbg(ans);
    for (int s : st) {
        ans = min(ans, tryst(s, ans));
        // dbg(ans);
    }
    printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);

    return 0;
}
